public class TestDemo14A {
    //计算二进制中1的个数

    public int NumberOf1(int n){
        int count=0;
        while(n!=0){
            n=n&(n-1);//循环多少次就说明有多少个1
            count++;
        }
        return count;
    }

    public static int NumberOf(int n){
        int count=0;
        while(n!=0){
            if((n&1)!=0){
                count++;
            }
            n=n>>>1;
        }
        return count;
    }

    public static void main2(String[] args) {
        int n=10;
        int tem=NumberOf(n);
        System.out.println(tem);
    }
    //输出倒数第k个节点
    public ListNode FindKthToTail(ListNode head,int k){
        if(head==null){
            return null;
        }
        ListNode front=head;
        ListNode rear=head;
        while(k>0&&front!=null){
            front=front.next;
            k--;
        }
        while(front!=null){
            front=front.next;
            rear=rear.next;
        }
        return k>0?null:rear;
    }

    //反转单链表(1. 定义三个指针，整体右移，边移动，边翻转，保证不会断链。)
    public ListNode reverseList(ListNode head){
        //链表只有一个节点或者没有头结点
        if(head==null||head.next==null){
            return head;
        }
        ListNode first=head;//第一个指针
        ListNode second=first.next;//第二个指针
        ListNode third=second.next;//第三个指针
        while(third!=null){
            second.next=first;//翻转
            first=second;//往后移
            second=third;//往后移
            third=third.next;//往后移
        }
        second.next=first;//如果链表只有两个节点要翻转或者是执行完之后最后两个节点的翻转
        head.next=null;//让尾节点置为空
        head=second;//重新定义头结点
        return second;
    }
    public static int A(int target){
        int []dp=new int [target+1];
        dp[0]=1;
        dp[1]=1;
        int i=0;
        for(i=2;i<=target;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        int tem=dp[target];
        return tem;
    }

    public static void main(String[] args) {
        int n=20;
        System.out.println(A(n));
    }

    public int rob1(int []nums){
        if(nums==null||nums.length==0){
            return 0;
        }
        int length=nums.length;
        int []dp=new int [length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<length;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+i);
        }
        return dp[length-1];
    }
//合并两个递增的单项链表,合并后也递增(方法一)
    public ListNode merge(ListNode list1,ListNode list2){
        //一个链表为空,返回另外一个
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode newHead=null;//定义头指针
        ListNode newEnd=null;//定义尾指针
        //合并中,无非是比较各自首节点谁小，就把该节点从原链表中删除，在尾插到新节点处，比较中，两个链表任何一个都不能为空
        while(list1!=null&&list2!=null){
            //把两个链表中小的值挑出来
            ListNode cur=list1.val>list2.val?list2:list1;
            if(cur==list1){
                list1=list1.next;
            }
            if(cur==list2){
                list2=list2.next;
            }
            if(newHead==null){//第一次插入需要重新定义头尾指针
                newHead=cur;
                newEnd=cur;
            }
            else{//第一次之后插入的值,采用尾插法,在尾指针的后面插入
                newEnd.next=cur;
                newEnd=cur;
            }
        }
        //当有一个链表遍历完之后,把另一个链表剩余的值直接插入
        if(list1==null){
            newEnd.next=list2;
        }
        if(list2==null){
            newEnd.next=list1;
        }
        return newHead;
    }
    //方法2
    public ListNode merge1(ListNode list1,ListNode list2){
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode newHead=new ListNode(-1);//定义傀儡节点
        ListNode tmp=newHead;
        while (list1!=null&&list2!=null){
            if(list1.val<list2.val){
                tmp.next=list1;
                tmp=tmp.next;
                list1=list1.next;
            }else {
                tmp.next=list2;
                tmp=tmp.next;
                list2=list2.next;
            }
        }
        if(list1==null){
            tmp.next=list2;
        }
        if(list2==null){
            tmp.next=list1;
        }
        return newHead.next;
    }
    //方法三(递归法)
    public ListNode merge2(ListNode list1,ListNode list2){
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode newHead=null;
        if(list1.val<list2.val){
            newHead=list1;
            list1=list1.next;
        }
        else{
            newHead=list2;
            list2=list2.next;
        }
        newHead.next=merge2(list1,list2);
        return newHead;
    }

    public boolean isSame(TreeNode begin,TreeNode begin_sub){
        if(begin_sub==null){//begin_sub为空,说明已经比较玩了
            return true;
        }
        if(begin==null){
            return false;//如果begin为空说明不匹配
        }
        if(begin.val!=begin_sub.val){
            return false;
        }
        return isSame(begin.left,begin_sub.left)&&isSame(begin.right,begin_sub.right);
    }
    public boolean HasSubtree(TreeNode root1,TreeNode root2){
        if(root1==null||root2==null){
            return false;
        }
        boolean result=false;
        if(root1.val==root2.val){
            result=isSame(root1,root2);//确定起始位置,从该位置与子树比较
        }
        if(result!=true){
            result=HasSubtree(root1.left,root2);
        }
        if(result==false){
            result=HasSubtree(root1.right,root2);
        }return result;
}
}

